package com.atguigu.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo2 {

    public static void main(String[] args) {

        //创建节点
        Student student = new Student(1, "李建国", "二狗");
        Student student2 = new Student(2, "杭双鹏", "炕板子");
        Student student3 = new Student(3, "赵明", "灯泡子");
//        Student student4 = new Student(4, "赵明", "灯泡子");
//        Student student5 = new Student(5, "赵明", "灯泡子");
//        Student student6 = new Student(6, "赵明", "灯泡子");
//        Student student7 = new Student(7, "赵明", "灯泡子");
//        Student student8 = new Student(8, "赵明", "灯泡子");
//        Student student9 = new Student(9, "赵明", "灯泡子");
//        Student student10 = new Student(10, "赵明", "灯泡子");

        //创建链表
        StudentLinkedList linkedList = new StudentLinkedList();


        //添加节点
//        linkedList.add(student);
//        linkedList.add(student2);
//        linkedList.add(student3);

        //测试有序且不重复添加节点方法
        linkedList.addOrderBy(student);
        linkedList.addOrderBy(student2);
        linkedList.addOrderBy(student3);
//        linkedList.addOrderBy(student4);
//        linkedList.addOrderBy(student5);
//        linkedList.addOrderBy(student6);
//        linkedList.addOrderBy(student7);
//        linkedList.addOrderBy(student8);
//        linkedList.addOrderBy(student9);
//        linkedList.addOrderBy(student10);

        //测试修改节点方法
        //Student studentUpdate = new Student(3, "赵明", "小灯泡");
        //linkedList.update(studentUpdate);

        //测试删除节点
        //linkedList.delete(2);

        //显示节点
        //linkedList.show();

        //统计有效节点个数
        //System.out.println("有效节点个数为: "+ Interview.getLength(linkedList.getHead()));

        //寻找倒数第K个节点
        //System.out.println("倒数第K个节点是: " + Interview.getStudent(linkedList.getHead(),3));

        //测试链表反转
        //Interview.reverseList(linkedList.getHead());
        //linkedList.show();

        //从尾到头打印链表
        Interview.reversesPrint(linkedList.getHead());


    }
}

//面试题
class Interview{

    /*统计链表中有效节点个数(不统计头节点)*/
    public static int getLength(Student head){

        //判断链表是否为空
        if (head.next == null){
            return 0;
        }

        Student temp = head.next;
        int count = 0;
        while (temp != null){
            count ++;
            temp = temp.next;
        }

        return count;
    }

    /*找到倒数第K个节点*/
    public static Student getStudent(Student head,int index){

        if (head.next == null){
            return null;
        }

        //获取有效节点个数
        int size = getLength(head);
        //对index进行基本校验
        if (index <= 0 || index > size){
            return null;
        }

        Student temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }

        return temp;
    }

    /*将单链表反转*/
    public static void reverseList(Student head){
        //如果单链表为null或者只有一个节点就不必反转
        if (head.next == null || head.next.next == null){
            return;
        }

        //定义辅助变量
        Student temp = head.next;
        //定义辅助链表
        Student reversLinked = new Student(0,"","");
        //定义当前节点的下一个节点
        Student next = null;

        while (temp != null){
            next = temp.next;

            temp.next = reversLinked.next;
            reversLinked.next = temp;
            temp = next;
        }

        head.next = reversLinked.next;
    }

    /*从尾到头打印单链表*/
    public static void reversesPrint(Student head){
        if (head.next == null){
            return;
        }

        //定义栈 利用先进后出的特点实现从尾到头打印链表
        Stack<Student> stack = new Stack<>();
        //定义辅助变量
        Student temp = head.next;
        //开始遍历
        while (temp != null){
            //每遍历一个元素,都push进栈中
            stack.push(temp);
            //后移元素
            temp = temp.next;
        }

        //遍历栈
      while (stack.size() > 0){
          System.out.println(stack.pop());
      }
    }
}

class StudentLinkedList {
    //头节点不能动
    private Student head = new Student(0, "", "");

    public Student getHead() {
        return head;
    }

    /*添加节点:每次在链表尾部插入节点*/
    public void add(Student student) {

        //定义辅助变量代替头节点去遍历
        Student temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }

            temp = temp.next;
        }

        //当退出while循环的时候,temp就指向了链表最后
        //将最后这个节点的next值指向新节点
        temp.next = student;

    }

    /*添加节点方法:对添加进来的节点进行一个有序排列且编号不可重复**/
    public void addOrderBy(Student student) {
        //1.声明辅助变量,代替头节点
        Student temp = head;
        //2.声明flag变量,如果编号重复为true
        boolean flag = false;
        //3.使用while循环,遍历链表
        while (true) {
            //4.判断是否到了链表尾部
            if (temp.next == null) {
                break;
            }

            //5.判断如果当前节点的下一个节点的编号大于传进来的节点编号,那么就说明找到了,结束循环
            if (temp.next.no > student.no) {
                break;
            }else if (temp.next.no == student.no) {
                flag = true;
                break;
            }

            temp = temp.next;
        }

        if (flag) {
            System.out.printf("添加失败!准备插入的学生编号 %d已经存在,不能加入\n",student.no);
        } else {
            student.next = temp.next;
            temp.next = student;
        }
    }

    /*根据编号修改节点*/
    public void update(Student student){

        //判断链表是否为空
        if (head.next == null){
            System.out.println("修改失败!链表为空~~");
            return;
        }

        Student temp = head.next;
        while (true){

            //说明已经到了链表尾部
            if (temp == null){
                break;
            }

            if (temp.no == student.no){
                temp.name = student.name;
                temp.nickName = student.nickName;
            }

            temp = temp.next;
        }
    }

    /*根据编号删除节点*/
    public void delete(int no){

        Student temp = head;
        boolean flag = false;
        while (true){

            if (temp.next == null){
                break;
            }

            if (temp.next.no == no){
                flag = true;
                break;
            }

            temp = temp.next;
        }

        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的 %d节点不存在 \n",no);
        }


    }

    /*显示链表*/
    public void show() {
        //判断链表是否为空,如果为空,直接提示链表为空
        if (head.next == null) {
            System.out.println("链表为空~~~");
            return;
        }

        //定义辅助变量代替链表头节点
        Student temp = head.next;
        while (true) {

            //判断链表是否到了最后
            if (temp == null) {
                break;
            }

            //打印当前节点
            System.out.println(temp);

            //节点向后移动
            temp = temp.next;
        }

    }

}

class Student {
    public int no;
    public String name;
    public String nickName;
    //下一节点
    public Student next;

    public Student(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "Student{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}